//
//  Heap.swift
//  LeetCodeDemo
//
//  Created by OS on 2022/8/3.
//

import Foundation


class Heap {
    
    var isMaxHeap: Bool
    var arr: [Int] = [Int]()
    var count: Int {
        return arr.count
    }
    var top: Int? {
        arr.first
    }

    init(isMaxHeap: Bool = true) {
        self.isMaxHeap = isMaxHeap
    }
    
    func compare(_ l: Int, _ r: Int) -> Bool {
        if isMaxHeap {
            return l > r
        }
        return l < r
    }

    /// 插入
    /// - Parameters:
    ///   - val: 值
    func insert(_ val: Int) {
        
        arr.append(val)
        var i = count - 1
        var index = (i - 1) / 2
        while index >= 0 && compare(arr[i], arr[index]) {
            arr.swapAt(i, index)
            i = index
            index = (i - 1) / 2
        }
        
    }
    
    @discardableResult
    /// 删除堆顶元素
    /// - Returns: 堆顶值
    func deleteTop() -> Int? {
        if count == 0 {
            return nil
        }
        let topVal = arr[0]
        arr[0] = arr[count - 1]
        _ = arr.popLast()
        
        heapify(&arr, count - 1, 0)
        
        return topVal
    }
    
    /// 堆化
    /// - Parameters:
    ///   - nums: 数组
    ///   - n: 数组长度 - 1
    ///   - i: 堆化下标
    func heapify(_ nums: inout [Int], _ n: Int, _ i: Int) {
        var i = i
        while true {
            var p = i
            let left = 2 * i + 1
            if left <= n && compare(nums[left], nums[p]) {
                p = left
            }
            let right = 2 * i + 2
            if right <= n && compare(nums[right], nums[p]) {
                p = right
            }
            if p == i {
                break
            }
            nums.swapAt(i, p)
            i = p
        }
    }
    
}






class MaxHeap {
    
    var arr: [Int] = [Int]()
    var count: Int {
        return arr.count
    }
    var top: Int? {
        arr.first
    }
    
    /// 插入
    /// - Parameters:
    ///   - val: 值
    func insert(_ val: Int) {
        
        arr.append(val)
        var i = count - 1
        var index = (i - 1) / 2
        while index >= 0 && arr[i] > arr[index] {
            arr.swapAt(i, index)
            i = index
            index = (i - 1) / 2
        }
        
    }
    
    
    @discardableResult
    /// 删除堆顶元素
    /// - Returns: 堆顶值
    func deleteTop() -> Int? {
        if count == 0 {
            return nil
        }
        
        let topVal = arr[0]
        arr[0] = arr[count - 1]
        _ = arr.popLast()
        
        heapify(&arr, count - 1, 0)
        
        return topVal
    }
    
    /// 堆化
    /// - Parameters:
    ///   - nums: 数组
    ///   - n: 数组长度 - 1
    ///   - i: 堆化下标
    func heapify(_ nums: inout [Int], _ n: Int, _ i: Int) {
        var i = i
        while true {
            var maxPos = i
            let left = 2 * i + 1
            if left <= n && nums[left] > nums[maxPos] {
                maxPos = left
            }
            let right = 2 * i + 2
            if right <= n && nums[right] > nums[maxPos] {
                maxPos = right
            }
            if maxPos == i {
                break
            }
            nums.swapAt(i, maxPos)
            i = maxPos
        }
    }
    
}


class MinHeap {
    
    var arr = [Int]()
    var count: Int {
        return arr.count
    }
    
    /// 插入
    /// - Parameters:
    ///   - val: 值
    func insert(_ val: Int) {
        
        arr.append(val)
        
        var i = count - 1
        var index = (i - 1) / 2
        while index >= 0 && arr[i] < arr[index] {
            arr.swapAt(i, index)
            i = index
            index = (i - 1) / 2
        }
        
    }
    
    
    @discardableResult
    /// 删除堆顶元素
    /// - Returns: 堆顶值
    func deleteTop() -> Int? {
        if count == 0 {
            return nil
        }
        let topVal = arr[0]
        arr[0] = arr[count - 1]
        _ = arr.popLast()
        
        heapify(&arr, count - 1, 0)
        
        return topVal
    }
    
    /// 堆化
    /// - Parameters:
    ///   - nums: 数组
    ///   - n: 数组长度 - 1
    ///   - i: 堆化下标
    func heapify(_ nums: inout [Int], _ n: Int, _ i: Int) {
        var i = i
        while true {
            var minPos = i
            let left = 2 * i + 1
            if left <= n && nums[left] < nums[minPos] {
                minPos = left
            }
            let right = 2 * i + 2
            if right <= n && nums[right] < nums[minPos] {
                minPos = right
            }
            if minPos == i {
                break
            }
            nums.swapAt(i, minPos)
            i = minPos
        }
    }
    
}
